package java_thinking.unit_16.source;

import java.util.Arrays;

/**
 * @Desc:   单向扫描划分方式
 *          必看：https://blog.csdn.net/Holmofy/article/details/71168530
 * @author: cww
 * @DateTime: 2019-04-23 22:15
 */

public class ForwardScanSort {
    public static void main(String[] args) {
        int[] a1 = {5,4,1,1,2,9,8,1,3,5,15,22,1,8};
        forwardScanSort(a1);
        System.out.println(Arrays.toString(a1));
    }
    public static void forwardScanSort(int[] items) {
        forwardScanSort(items, 0, items.length - 1);
    }

    /**
     * 前面的i，j标记都是相向而行，i标记负责找比pivot大的元素，j标记负责比pivot小的元素
     * @param items
     * @param start
     * @param end
     */
    public static void forwardScanSort(int[] items, int start, int end) {
        if (start < end) {
            int pivot = items[start];
            int i = start, j = start + 1;
            while (j <= end) {
                if (items[j] < pivot) {
                    i++;
                    //有时候i=j，自己替换自己无所谓
                    swap(items,i,j);
                }
                j++;
            }
            swap(items,start,i);
            forwardScanSort(items,start,i - 1);
            forwardScanSort(items,i + 1,end);
        }
    }

    public static void div3ScanSort(int[] items) {
        div3ScanSort(items, 0, items.length - 1);
    }
    public static void div3ScanSort(int[] items, int start, int end) {
        if (start < end) {
            int pivot = start;
            int i = start, k = start + 1, j = end;
            OUT_LOOP :while (k < j) {
                if (items[k] < pivot) {
                    swap(items, i, k);
                    i++;
                    k++;
                }else if (items[k] == pivot) {
                    k++;
                } else {
                    //items[k] > pivot
                    while (items[j] > pivot) {
                        j--;
                        if (k > j) {
                            break OUT_LOOP;
                        }
                    }
                    //有可能items[j]是小于pivot的
                    if (items[j] < pivot) {
                        swap(items, k, j);
                        swap(items, i, k);
                    } else {
                        swap(items, k, j);
                    }
                    k++;
                }
                div3ScanSort(items, start, i-1);
                div3ScanSort(items, j+1, end);
            }
        }
    }
    public static void swap(int[] items, int i, int j) {
        int tmp = items[i];
        items[i] = items[j];
        items[j] = tmp;
    }
}
